// 快速排序
let arr = [5, 3, 4, 6, 2, 8, 7, 9, 1];

/** 
 * 简单实现
 */
const quick_sort_v1 = function (arr, l, r) {
  // 结束条件
  if (l >= r) return;
  let x = l,  // 左指针
    y = r,  // 右指针
    // 基准值：取最左边的值
    base = arr[l];

  while (x < y) {
    // 找到右边小于基准值的值
    while (x < y && arr[y] >= base) y--;  // x < y : 防止指针移动过程中两指针相遇
    // 将右边小于基准值的值放到左边的空位
    if (x < y) arr[x++] = arr[y];

    // 找到左边大于基准值的值
    while (x < y && arr[x] <= base) x++;
    // 将左边大于基准值的值放到右边的空位
    if (x < y) arr[y--] = arr[x];
  }
  // 将基准值放到最后的空位
  arr[x] = base;

  quick_sort_v1(arr, l, x - 1);
  quick_sort_v1(arr, x + 1, r);
}

quick_sort_v1(arr, 0, arr.length - 1);
console.log(arr);

/**
 * 单边递归法实现
 */
const quick_sort_v2 = function (arr, l, r) {
  // 外层循环代替递归
  while (l < r) {
    let x = l, y = r, base = arr[l];
    // 内层循环不变
    while (x < y) {
      while (x < y && arr[y] >= base) y--;
      if (x < y) arr[x++] = arr[y];

      while (x < y && arr[x] <= base) x++;
      if (x < y) arr[y--] = arr[x];
    }
    arr[x] = base;  // 将基准值放到最后的空位

    quick_sort_v2(arr, x + 1, r);
    r = x - 1;
  }
}
// quick_sort_v2(arr, 0, arr.length-1);
// console.log(arr);

/**
 * 三点取中间 + 插入排序 + 单边递归
 */

// 取中间值， 三点取中间
function median(a, b, c) {
  if (a > b) [a, b] = [b, a];
  if (a > c) [a, c] = [c, a]; // a最小值
  if (b > c) [b, c] = [c, b]; // 比较 b，c
  return b;
}

const threshold = 3;
const __quick_sort_v3 = function (arr, l, r) {
  while (r - l > threshold) {
    let x = l, y = r, base = median(arr[l], arr[(l + r) >> 1], arr[r]);
    do {
      while (arr[x] < base) x++;
      while (arr[y] > base) y--;
      if (x <= y) {
        [arr[x], arr[y]] = [arr[y], arr[x]]; // 交换值
        x++;
        y--;
      }
    } while (x <= y);

    __quick_sort_v3(arr, x, r);
    r = y;
  }
}

// 插入排序
const final_insert_sort = function (arr, l, r) {
  /** 将最小值放到最左边当哨兵 */
  // 记录最小值
  let ind = l;
  // 查找最小值下标 O(n)
  for (let i = 1; i <= r; i++) {
    if (arr[i] < arr[ind]) ind = i;
  }

  // 将最小值移动到最左边， 减少特判 
  // 将最小值移动到最左边 > O(n)
  while (ind > l) {
    // 交换 ind 和 ind - 1
    [arr[ind], arr[ind - 1]] = [arr[ind - 1], arr[ind]];
    ind--;
  }

  // 插入排序
  for (let i = l + 2; i <= r; i++) {
    let j = i; // i: 当前插入的元素, j: 与当前元素比较的元素
    while (arr[j] < arr[j - 1]) {     //  如果没有减少特判的优化，这里需要加上 j >= l
      // 交换 i 和 j - 1
      [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
      j--;
    }
  }
}

const quick_sort_v3 = function (arr, l, r) {
  __quick_sort_v3(arr, l, r);
  final_insert_sort(arr, l, r);
}

// quick_sort_v3(arr, 0, arr.length-1);
